package interview;

public class Test {

  public int test(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    /**
     * 将正数放入正数堆，负数放入负数堆，然后求解两堆的最小差值
     * 转化为01背包问题
     * 在背包容量为m/2的前提下，向背包中装入石头，使得背包价值最高
     */
    int len = nums.length;
    int[][] dp = new int[len][sum / 2 + 1];
    // 初始化
    for (int j = 0; j <= sum / 2; j++) {
      dp[0][j] = (nums[0] > j) ? 0 : nums[0];
    }
    // 遍历
    for (int i = 1; i < len; i++) {
      for (int j = 0; j <= sum / 2; j++) {
        if (nums[i] > j) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
        }
      }
    }
    // 总容量-最大背包数目=负数堆  负数堆-最大背包数目得到差值
    return Math.abs((sum - dp[len - 1][sum / 2]) - dp[len - 1][sum / 2]);
  }

  public static void main(String[] args) {
    int test = new Test().test(new int[]{3, 4, 1, 6, 7});
    System.out.println(test);
  }
}